import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}

public class Solution {
    // 根据二叉树创建字符串
    // 你需要采用前序遍历的方式，将一个二叉树转换成一个由括号和整数组成的字符串。
    //空节点则用一对空括号 "()" 表示。
    // 而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对
    // 括号省略原则
    // 如果一个节点的左右子树都为空，两个括号都可以省略
    // 如果左子树为空，右子树不为空，括号不能省略
    // 如果右子树为空，左子树不为空，括号可省略
    public StringBuffer stringBuffer = null;
    public String tree2str(TreeNode t) {
        stringBuffer = new StringBuffer();
        if (t == null) {
            return stringBuffer.toString();
        }
        _tree2str(t);
        stringBuffer.deleteCharAt(0);
        stringBuffer.deleteCharAt(stringBuffer.length() - 1);
        return stringBuffer.toString();
    }

    private void _tree2str(TreeNode t) {
        if (t == null) {
            return;
        }
        stringBuffer.append("(");
        stringBuffer.append(t.val);
        if (t.left == null && t.right != null){
            stringBuffer.append("()");
        }
        _tree2str(t.left);
        _tree2str(t.right);
        stringBuffer.append(")");
    }

    // 从前序与中序遍历序列构造二叉树
    // 根据一棵树的前序遍历与中序遍历构造二叉树。
    // 注意:你可以假设树中没有重复的元素。
    private int index = 0;
    public TreeNode buildTree1(int[] preorder, int[] inorder) {
        index = -1;
        List<Integer> list = new ArrayList<>();
        for (int x : inorder) {
            list.add(x);
        }
        return _buildTree1(preorder, list);
    }

    private TreeNode _buildTree1(int[] preorder, List<Integer> list) {
        if (list.isEmpty() == true) {
            return null;
        }
        index++;
        TreeNode root = new TreeNode(preorder[index]);
        int pos = list.indexOf(preorder[index]);
        root.left = _buildTree1(preorder, list.subList(0, pos));
        root.right = _buildTree1(preorder, list.subList(pos + 1, list.size()));
        return root;
    }

    // 从中序与后序遍历序列构造二叉树
    // 根据一棵树的中序遍历与后序遍历构造二叉树。
    // 注意:你可以假设树中没有重复的元素。
    private int index1 = 0;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        index1 = inorder.length;
        List<Integer> list = new ArrayList<>();
        for (int x : inorder) {
            list.add(x);
        }
        return _buildTree(list, postorder);
    }

    private TreeNode _buildTree(List<Integer> list, int[] postorder) {
        if (list.isEmpty() == true) {
            return null;
        }
        index1--;
        TreeNode root = new TreeNode(postorder[index1]);
        int pos = list.indexOf(postorder[index1]);
        root.right = _buildTree(list.subList(pos + 1, list.size()), postorder);
        root.left = _buildTree(list.subList(0, pos), postorder);
        return root;
    }

    // 非递归，二叉树的前序遍历
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        stack.push(cur);
        while (stack.isEmpty() == false) {
            cur = stack.pop();
            ret.add(cur.val);
            if (cur.right != null) {
                stack.push(cur.right);
            }
            if (cur.left != null) {
                stack.push(cur.left);
            }
        }
        return ret;
    }

    // 非递归，二叉树中序遍历
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        // 1. 先搞一个栈
        Stack<TreeNode> stack = new Stack<>();
        // 2. 创建一个 cur 从 root 开始执行
        TreeNode cur = root;
        // 3. 第一层循环. 负责从栈里取元素
        while (true) {
            // 第二层循环. 负责往栈里插入元素
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            if (stack.isEmpty()) {
                // 如果栈为空, 就直接结束循环
                break;
            }
            // 栈不为空, 就取出栈顶元素并访问
            cur = stack.pop();
            ret.add(cur.val);
            // 让 cur 指向 top 的右子树, 继续重复执行上述过程
            cur = cur.right;
        }
        return ret;
    }

    // 非递归，二叉树的后序遍历
    // 方法一，由于镜像二叉树的先序遍历=原二叉树后序遍历
    // 所以我们先序遍历该树的镜像二叉树（根 右 左），将遍历结果颠倒（栈）就是后续遍历的结果
    public List<Integer> postorderTraversal1(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        Stack<TreeNode> stack = new Stack<>();
        Stack<Integer> tmp = new Stack<>();
        TreeNode cur = root;
        stack.push(cur);
        while (stack.isEmpty() == false) {
            cur = stack.pop();
            tmp.push(cur.val);
            if (cur.left != null) {
                stack.push(cur.left);
            }
            if (cur.right != null) {
                stack.push(cur.right);
            }
        }
        while (tmp.isEmpty() == false) {
            ret.add(tmp.pop());
        }
        return ret;
    }

}
